#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 交换函数，用于交换数组中两个元素的位置
void swap(vector<int>& a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

// 构建堆
vector<int> heap(vector<int>& nums) {
    vector<int> h(nums.size() + 1);
    for (int i = 0; i < nums.size(); ++i) {
        h[i + 1] = nums[i];
        for (int k = i + 1; k > 1 && h[k] > h[k / 2]; swap(h, k, k / 2), k /= 2) {}
    }
    return h;
}

// 堆排序
vector<int> heapSort(vector<int>& h) {
    cout << "堆排序开始：" << endl;
    int n = h.size() - 1;
    int step = 1;
    for (int k = n; k >= 2; k--) {
        int i = 1;
        swap(h, i, k);
        while (i < k) {
            int j = i * 2;
            if (j + 1 < k && h[j + 1] > h[j])
                j = j + 1;
            if (j < k && h[j] > h[i]) {
                swap(h, i, j);
                i = j;
            }
            else
                break;
        }
        cout << "第" << (step++) << "步:" << display(h, 1) << endl;
    }
    return h;
}

// 用于展示数组元素内容的函数，从指定索引开始输出元素
string display(vector<int>& arr, int start) {
    string result;
    for (int i = start; i < arr.size(); ++i)
        result += "\t" + to_string(arr[i]);
    return result;
}

int main() {
    vector<int> nums = { 24, 61, 7, 92, 4, 6, 44 };
    cout << "原数组：\n" << display(nums, 0) << "\n" << endl;

    // 构建堆
    vector<int> h = heap(nums);
    cout << "构建出来的堆为：\n" << display(h, 1) << "\n" << endl;

    // 堆排序
    h = heapSort(h);
    cout << "\n最终堆排序结果为: \n" << display(h, 1) << "\n" << endl;

    return 0;
}